package divideconquer;

import java.util.Random;

public class MergeSort {

	static int[] buf;
	static int inverseCnt;

	public static void mergeSort(int[] a) {
		int n = a.length;
		buf = new int[n];
		inverseCnt = 0;
		sort(a, 0, n - 1);
	}

	static void sort(int[] a, int i, int j) {
		if (i == j)
			return;
		int m = i + j >> 1;
		sort(a, i, m);
		sort(a, m + 1, j);
		merge(a, i, j, m);
	}

	static void merge(int[] a, int i, int j, int m) {
		int p = i, q = m + 1;
		int idx = i;
		while (p <= m && q <= j) {
			if (a[p] <= a[q]) {
				buf[idx++] = a[p++];
			} else {
				inverseCnt += q - idx;
				buf[idx++] = a[q++];
			}
		}
		while (p <= m) {
			buf[idx++] = a[p++];
		}
		while (q <= j) {
			buf[idx++] = a[q++];
		}
		while (i <= j) {
			a[i] = buf[i++];
		}
	}

	public static void main(String[] args) {
		int n = 5;
		int[] a = new int[n];
		Random ran = new Random();
		for (int i = 0; i < n; ++i) {
			a[i] = ran.nextInt(100);
		}
		mergeSort(a);
		for (int i : a) {
			System.out.print(i + " ");
		}
	}

}
